package training;

/**
 * @Author liangzai
 * @Description:
 */
public class J25_7_3_Training {
    //统计隐藏数组数目
    public int numberOfArrays(int[] differences, int lower, int upper) {
        int start = binarySearch(differences, lower, upper, true);
        int end = binarySearch(differences, lower, upper, false);
        return start == lower - 1 || end == lower - 1 ? 0 : end - start + 1;
    }

    private int binarySearch(int[] diffs, int lower, int upper, boolean leftBound) {
        int left = lower, right = upper, ans = lower - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            int state = check(diffs, lower, upper, mid);
            if (state == 0) {
                ans = mid;
                if (leftBound) right = mid - 1;
                else left = mid + 1;
            }
            else if (state == -1) left = mid + 1;
            else right = mid - 1;
        }
        return ans;
    }

    private int check(int[] diffs, int lower, int upper, int s) {
        for (int diff : diffs) {
            s += diff;
            if (s < lower) return -1;
            if (s > upper) return 1;
        }
        return 0;
    }
}
